掌握动态规划的基本模板

无论问题多复杂，大多数 DP 问题遵循以下模板：

1. 定义状态：用 dp[i] 表示子问题的解。

例如，背包问题中，dp[i][w] 表示前 i 个物品在总重量 w 下的最大价值。

2. 状态转移方程：根据问题定义找到状态之间的关系。

例如，背包问题中，转移方程是： dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i] + v_i)

3. 初始化状态：设置基本的边界条件。

例如，所有重量为 0 的状态，价值都是 0

4. 确定计算顺序：从基础状态开始递推。
5. 输出结果：一般是 dp[n] 或 dp[n][W]。